package hot100;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class isValid {
    public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 != 0) {
            return false;
        }

        Map<Character, Character> pairs = new HashMap<Character, Character>() {
            {
                put(')', '(');
                put(']', '[');
                put('}', '{');
            }
        };
        Deque<Character> stack = new LinkedList<Character>();
        for(int i = 0;i < n;i++) {
            char a = s.charAt(i);
            if(pairs.containsKey(a)){
                if(stack.isEmpty() || stack.peek() != pairs.get(a)) {
                    return false;
                }
                stack.pop();
            }else {
                stack.push(a);
            }
        }
        return stack.isEmpty();

    }
}
